package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/missing-number/description/">丢失的数字</a>
 * <p>给定一个包含[0, n]中 n个数的数组nums ，找出[0, n]这个范围内没有出现在数组中的那个数。
 * <pre>
 * 示例 1：
 *      输入：nums = [3,0,1]
 *      输出：2
 *      解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 *
 * 示例 2：
 *      输入：nums = [0]
 *      输出：1
 *      解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
 * </pre>
 * <b>提示：</b>
 * <li>n == nums.length</li>
 * <li>1 <= n <= 10^4</li>
 * <li>0 <= nums[i] <= n</li>
 * <li>nums 中的所有数字都 独一无二</li>
 *
 * @author c2b
 * @since 2022/5/19 16:38
 */
public class LC0268MissingNumber_S {

    /**
     * 丢失的数字
     *
     * @param nums 数组
     * @return int 消失的数字
     * @author c2b
     * @since 2022/5/19 16:39
     */
    public int missingNumber(int[] nums) {
        int[] ints = new int[nums.length + 1];
        for (int num : nums) {
            ints[num] = 1;
        }
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] != 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 因为是连续的数字,可以用等差数列公式
     *
     * @param nums 数组
     * @return int 消失的数字
     * @author c2b
     * @since 2022/5/19 16:46
     */
    public int missingNumber2(int[] nums) {
        int length = nums.length;
        // (首项+末项) * 项数 / 2
        // 首项是0，末项是length 。 项数是length+1
        int total = (length * (length + 1)) >> 1;
        int arrSum = 0;
        for (int num : nums) {
            arrSum += num;
        }
        return total - arrSum;
    }
}
